package com.lizk.tree;

import org.apache.commons.lang3.tuple.Pair;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分搜索树
 * 1.每个节点的值大于左孩子
 * 2.每个节点的值小于右孩子
 * 3.左右子树仍为二分搜索树
 * 4.二分搜索树不一定是完全二叉树(除了最后一个非叶子结点可以不满，其他的节点都有左右孩子)
 * @author lizhikui
 * @date 2020/2/10 11:20
 */
public class BinarySearchTree <K extends Comparable<K>,V>{

    /**
     * 二叉搜索树的节点
     */
    public static class Node <K ,V>{
        K key;
        V value;
        Node<K,V> left;
        Node<K,V> right;
        public Node(K key,V value){
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
        }

        @Override
        public int hashCode() {
            return key.hashCode();
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Node){
                return key.equals(((Node)obj).key);
            }else{
                return false;
            }
        }
    }

    /**
     * 搜索树中第一个结点
     */
    Node<K,V> root;
    /**
     * 搜索树中结点的个数
     */
    int size;

    public BinarySearchTree(){
        root = null;
        size = 0;
    }


    /**
     * 直接使用循环来插入node
     * @param target 要插入的节点
     */
    public void insert(Node<K,V> target){
        add(target);
    }

    private void add(Node<K,V> target){
        if (root == null){
            root = target;
            size ++;
            return ;
        }
        Node<K,V> tmpNode = root;
        while (true){
            if ( target.key.compareTo(tmpNode.key) < 0){
                if (tmpNode.left == null){
                    tmpNode.left = target;
                    size ++;
                    return;
                }else{
                    tmpNode = tmpNode.left;
                }
            }else if (0 < target.key.compareTo(tmpNode.key)){
                if (tmpNode.right == null){
                    tmpNode.right = target;
                    size ++;
                    return;
                }else{
                    tmpNode = tmpNode.right;
                }
            }else {
                tmpNode.value = target.value;
                return;
            }
        }
    }


    /**
     * 使用递归的方式插入node
     * @param node  要插入的节点
     */
    public void insert2(Node<K,V> node){
        this.root = addNodeAfter(root,node);
    }

    private Node<K,V> addNodeAfter(Node<K,V> root, Node<K,V> target){
        if (root == null){
            root = target;
        }else if (target.key.compareTo(root.key)<0){
            root.left = addNodeAfter(root.left,target);
        }else if(target.key.compareTo(root.key)>0){
            root.right = addNodeAfter(root.right,target);
        }else{
            root.value = target.value;
        }
        return root;
    }

    public boolean contain(K key){
        Node<K,V> result = search(key);
        return result != null;
    }

    public Node<K,V> search(K key){
        Node<K,V> tmpNode = root;
        while (tmpNode != null){
            if (key.compareTo(tmpNode.key) < 0){
                tmpNode = tmpNode.left;
            }else if (key.compareTo(tmpNode.key) > 0){
                tmpNode = tmpNode.right;
            }else {
                return tmpNode;
            }
        }
        return null;
    }


    private Pair<Node<K,V>,Node<K,V>> minTwoValue(Node<K,V> node){
        if (node == null)
            return null;
        Node<K,V> lastSecondNode = null;
        Node<K,V> lastFirstNode = node;
        while (true){
            if (lastFirstNode.left == null){

                return Pair.of(lastSecondNode,lastFirstNode);
            }
            lastSecondNode = lastFirstNode;
            lastFirstNode = lastFirstNode.left;
        }
    }

    public void delNode(K k){
        Node<K, V> node = root;

        Node<K,V> parentNode = null;

        int leftOrRight = -1;
        while (true){
            if (node == null){
                return;
            }
            if (k.compareTo(node.key) < 0 ){
                parentNode = node;
                leftOrRight = -1;
                node = node.left;
            }else if (k.compareTo(node.key) > 0 ){
                parentNode = node;
                leftOrRight = 1;
                node = node.right;
            }else {
                if (node.left == null){
                    if (parentNode == null){
                        root = node.right;
                    }else if (leftOrRight == -1){
                        parentNode.left = node.right;
                    }else{
                        parentNode.right = node.right;
                    }
                } else if (node.right == null){
                    if (parentNode == null){
                        root = node.right;
                    }else if (leftOrRight == -1){
                        parentNode.left = node.left;
                    }else{
                        parentNode.right = node.left;
                    }
                }else {

                    Pair<Node<K, V>, Node<K, V>> pair = minTwoValue(node.right);
                    Node<K, V> secondMinValue = pair.getKey();
                    Node<K, V> firstMinValue = pair.getValue();

                    if (parentNode == null){
                        root = firstMinValue;
                    }else if (leftOrRight == -1) {
                        parentNode.left = firstMinValue;
                    }else {
                        parentNode.right = firstMinValue;
                    }
                    firstMinValue.left = node.left;
                    if (secondMinValue != null){
                        secondMinValue.left = null;
                        firstMinValue.right = node.right;
                    }
                }
                size--;
                return;
            }
        }

    }

    /**
     * 查找搜索树种最大值
     */
    public Node<K,V> maxValue(){
        return maxValue(root);
    }

    public Node<K,V> maxValue(Node<K,V> node){
        if (node == null)
            return null;
        Node<K,V> tmpNode = node;
        while (true){
            if (tmpNode.right == null){
                return tmpNode;
            }
            tmpNode = tmpNode.right;
        }
    }

    /**
     * 查找搜索树中最小值
     */
    public Node<K,V> minValue(){
        return minValue(root);
    }
    private Node<K,V> minValue(Node<K,V> node){
        if (node == null)
            return null;
        Node<K,V> tmpNode = node;
        while (true){
            if (tmpNode.left == null){
                return tmpNode;
            }
            tmpNode = tmpNode.left;
        }
    }

    /**
     * 前序遍历
     * @param node
     */
    public void preTraverse(Node node){
        if (node != null){
            System.out.println(node.value);
            preTraverse(node.left);
            preTraverse(node.right);
        }
    }


    /**
     * 中序遍历
     * @param node
     */
    public void inTraverse(Node node){
        if (node != null){
            inTraverse(node.left);
            System.out.println(node.value);
            inTraverse(node.right);
        }
    }

    /**
     * 后序遍历
     * @param node
     */
    public void postTraverse(Node node){
        if (node != null){
            postTraverse(node.left);
            postTraverse(node.right);
            System.out.println(node.value);
        }
    }

    /**
     * 广度优先的循环实现
     */
    public void breadthFirstTraverseByXunHuan(){
        List<Node> nodeList = new ArrayList<>();
        if (root != null){
            nodeList.add(root);
        }
        while(nodeList.size() > 0){
            Node node = nodeList.get(0);
            nodeList.remove(0);
            if (node.left != null){
                nodeList.add(node.left);
            }
            if (node.right != null){
                nodeList.add(node.right);
            }
            System.out.println(node.value);
        }
    }

    /**
     * 广度优先的递归实现
     */
    public void breadthFirstTraverseByDiGUI(){
        List<Node> nodeList = new ArrayList<>();
        if(root != null){
            nodeList.add(root);
            breadthFirstTraverseDeal(nodeList);
        }
    }

    private void breadthFirstTraverseDeal(List<Node> nodeList){
        if (nodeList != null && nodeList.size() > 0){
            Node node = nodeList.get(0);
            nodeList.remove(0);
            if (node.left != null){
                nodeList.add(node.left);
            }
            if (node.right != null){
                nodeList.add(node.right);
            }
            System.out.println(node.value);
            breadthFirstTraverseDeal(nodeList);
        }
    }

}
